/**
/// @file there are lots of problems solved by me during the period of
///       from 25th of September to 8th of October  (I was toiling to cope with the
///       problems (some of them were really difficult for me due to my
          weak knowledge of C so I didn't  succeed to do all of them in time therefore
          I'm presenting to you the problems now
///
/// @author Berenkov Nikita
///
/// @version 1.1.0

*/

/// After that 10 functions(e.g. problemX() )  should be written and each of them
///    is referred to the each problem


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<assert.h>


const int YES = 1;
const int  NO = 0;
int const MAXLINES = 200;

struct student{
char name[20];
char mark;
};
//{============================================================================================

/**
 @brief     There is the function which is sorting the massive of points

 @code      void qsortic (student* a,char *lines[],int left,int right );

 @param     *a - the point to the massive of structures STUDENT
            *lines[] - the massive of points
            left,right - the borders of the sorting

 @code       void swapp( student* a,char*lines[], int i,int j);
 @brief      this function swaps two members in the massive

 @code       void swap_str(char *lines[], int num1,int num2);
 @brief      the function swaps two lines

*/

 void qsortic (student* a,char *lines[],int left,int right );

 void swapp( student* a,char*lines[], int i,int j);

 void swap_str(char *lines[], int num1,int num2);
//{==============================================================================================

 /**
    @brief    There are three functions:

    @code     int swapping(char *a, char *b)

    @brief    This function swaps two char symbols
    @param     a - address of the first char symbol
               b - address of the second


    @code     int reverse_stroka(char str[])
    @brief     this function is turning all words in the line over
    @param     str[] -the line


    @code     int reverse_word(char str[], int left, int right)
    @param     str[] - the line
           left - the left border symbol
            right - the right bordeer symbol
*/
/**


*/
 int swapping(char *a, char *b);

 int reverse_stroka(char str[]);

 int reverse_word(char str[], int left, int right);

 int weighing(long x);

 int del (int n);

 int decompose(int n,int k);

 int normalize_sqrt(long n, long int * a, long int * b);

 int delnew (int n );

 int prostoe(int v);

 int problem1();

 int problem2();

 int problem3();

 int problem4();

 int problem5();

 int problem6();

 int problem7();

 int problem8();

 int problem9();

 int problem10();

 struct student a[100];


 int main()
 {


//fseek(fp,0,SEEK_END);
//long sizek = ftell(fp);

    int p = 0;
    scanf("%d",&p);
    switch(p)
    {
      case 1: problem1(); break;//This program is sorting the students

      case 2: problem2(); break;//This program define if there are any full squares in the number

      case 3: problem3(); break;//This program outputs the sequence of prime numbers from the massive

      case 4: problem4(); break;//This program filters the lines

      case 5: problem5(); break;//This program gets out the N st prime number

      case 6: problem6(); break;//this program makes the strings overturn

      case 7: problem7(); break;//this program about calculation the amount of numbers

      case 8: problem8(); break;//This program about decomposition

      case 9: problem9(); break;//This program normalizes the square root

      case 10: problem10(); break;//This program defines whether it is possible to
                                   //weigh the number or not

      default : printf("The user ain't wanna solve problems");break;



    }


 }


//! @brief
/// this function solves the problem about sorting the students in the correct order


int problem1()
{
    char *lines[MAXLINES];
 int i=0;
 char* s;
 int k=0;
 int j=0;
 char s1[2];
 int e=0;



FILE *fp;
FILE *fpout;
if ((fpout = fopen("output.txt","w"))==NULL)
{
printf("can't open\n");
exit(1);
}


if((fp = fopen("input.txt", "r"))==NULL)
    {
printf ("Cannot open file.\n");
exit(1);
    }
fclose(fpout);
fpout = freopen("output.txt","w",stdout);
//fseek(fp,0,SEEK_END);
//long sizek = ftell(fp);

int n=0;


fscanf(fp, "%d\n", &n);
//fprintf(fpout,"%d",n); /*the adjustment*/

for (int u=0;u<n;u++)
{

if (!(s = (char*) calloc( 100, sizeof(char)) ) )
{
    printf("Allocation error");
    exit(0);
}
else
{

if (!(fgets(s,100,fp)) && (fgets(s,100,fp)!=NULL))
{
    printf("NO it's stopped ");
    exit(0);
}


//printf(fpout,"%s",s);
//fprintf(fpout,"\n");
//int k=strlen(s);
//for(i=0;i<k;i++)



//free(s);
//}
 e=0;
 i=0;
int l=strlen(s);
//intf("%d\n",l);
   while(s[i]!=' ')
    {
  a[j].name[e] = s[i];
  e++;
   i++;
    }

    lines[j] = a[j].name;


 for (i=0;i<l;i++)
    if (isdigit(s[i]))
    a[j].mark = s[i];
    printf("%s %c\n",lines[j],a[j].mark);

j++;

free(s);

}
}

    /* char *f;
      f = lines[1];
      lines[1] = lines[2];
      lines[2] = f;*/

//swap_str(lines,1,2);
printf("%d\n",n);
qsortic(a,lines,0,n);
//swapp(a,lines,1,2);*/


for (i=0;i<n;i++)

   printf("%s %c\n",lines[i],a[i].mark);

}


//! @brief   this function solves the problem  about figuring out whether the number
///         consist of full squares or not .
///         As an answer the problem outputs the word "YES" or "NO" if the number consists some full squares
///         or no  and the sequence of full squares

int problem2()
{ int n;
    scanf("%d",&n);
del(n);
//printf("%d",(int)sqrt(n) );
}

//! @brief This function solves the problem which outputs the sequence of prime numbers from the
///        massive in the beginning

int problem3(void)
{

int c,k,i,n;
/**
@brief   this programme gets as an input the massive of nombers
            and outputs only prime nombers

**/
///  Here write in the amount of members in massive
///  After that on the new line write massive of nombers
///  divided from each other with gaps

 scanf("%d",&c);

int a[100];
for (i=0;i<c;i++)
{
    scanf("%d", &n);
    a[i]=n;

}

for(i=0;i<c;i++)
    prostoe(a[i]);



}


//! @brief this function is realizing the solution of the problem about filtering the lines
///        of symbols
///

int problem4(void)

{   int t = 0;
    char c = '\0';
    int o = 0;
    char s[100] = "";
    char s1[100] = "";
    char u;
 if (t == 0) {

      printf("print here the new line\n");
getchar();
    while ((c = getchar())!='\n')

{
       s[o] = c;
       o++;
}

o=strlen(s);
int i = 0;
int j = 0;
while ( i < o)


{


if (isspace( s[i] ))
    {
        do (i++) ;
        while (s[i] == ' ');
      s1[j] = ' ';i--;

    }
   // else {s1[j]=s[i];j++;}
        else if (isdigit(s[i]))
            {
                s[i] = '#';
                s1[j] = s[i];

            }
            else if (isupper(s[i]))
                {
                    tolower(s[i]);
                    s1[j] = s[i];
                }
                    else if (ispunct(s[i]) ) j--;
                    else

                        s1[j] = s[i];
                        i++;
                        j++;

}
o = strlen(s1);
printf("%d\n",o);

    for (int i = 0;i<o;i++)
        printf("%c",s1[i]);
        printf("\n");
     }

}


///{=============================================================================================
/// @brief       this program is getting out the n st prime nomber
/// @param[in]    m - the num of the prime number
/// @param[out]    o - the prime number
///{===============================================================================================

int problem5()
{
  //int a[];
int m;
int b=false;    //int n;
long o;
long i;
int  n = 100;
///Put here the nomber of prime num
   scanf("%d",&m);
   int a[n];

   a[0] = a[1] = false;

for( i=2;i <= n;i = i+1)
a[i] = true;



for ( i = 2;i*i <= n; i = i+1)
    if (a[i]==true)
    for (int j=i*i;j<=n;j=j+i)

    a[j] = false;
    int k = 0;
    //for (i=0;i<n;++i)
       // printf("%d",a[i]);
    for (i = 2;i < n;++i) {
        if (a[i] == true)
        {
         o = i;
        ++k;

        }
    if (k == m)
    { printf("%d",o);
    break;

    }
  }
}


/**  @brief  This program is making overturn of lines
that's crucial important: YOU MUST PUT THE SYMBOL ' ' AFTER THE LINE !!!
*/
int problem6(void)
{
    char s[1000]="";//<
    int o=0;
    int i=0;
    int  c='0';
//printf("%c",c);
//c=getchar();
getchar();
while ((c=getchar())!='\n')

{
    s[o]=c;
    o++;

}
reverse_stroka(s);

}

/**
/// @brief this function solves the problem about calculation the amount of numbers with the
          fixed quantity of members and fixed sum of members

*/
long int amount (int *a,int n,int k);

int problem7(void)
{
    int n = 0;
    int k = 0;

  int *a;
  a = (int*) calloc(100,sizeof(int));

  scanf("%d%d", &n, &k);
  printf("%d",amount (a,n,k));

free(a);

}

long int amount (int *a,int n,int k)
{int m;
int s=0;
int i = 0;
if ((n<0) || (k<0)) return 0;
else
if (k == 1)
{
    if (n <= 9) return 1;
    else if (n>9) return 0;
}

else if (k==0)
{
        if (n==0) return 1;
        else return 0;
}
else if ((n==0))
{
    if ((k==0)|| (k==1)) return 1;
    else  return 0;}
else
    return amount (a,n,k-1) + amount (a,n-1,k-1) + amount (a,n-2,k-1) +amount (a,n-3,k-1) +amount (a,n-4,k-1)
    +amount (a,n-5,k-1) +amount (a,n-6,k-1) +amount (a,n-7,k-1) +amount (a,n-8,k-1) +amount (a,n-9,k-1);


}

/**
This problem about decomposition of the number to the items
As an answer the program prints the quantity of the methods
*/

int problem8()
{
    int n = 0;
scanf("%d",&n);
printf("%d",decompose(n,n));



}
/**
This function solves the problem about normalization of the square root
*/

int problem9()
{
    long n=0;
    long a;
    long b;


    scanf("%d",&n);

    normalize_sqrt( n,&a,&b);
    printf("%d %d",a,b);


}

/**
This function solves the problem about weighing (problem C v1)

*/

int problem10()
{
        long a = 0;

        printf("Write x number which we want weigh(0 < x < 2^31)\n");

        while (!scanf("%d", &a))
        {
            while(getchar() != '\n');
            printf("Write x number which we want weigh(0 < x < 2^31)\n");
        }

        printf((weighing(a) == YES)? "YES, you can weight it\n": "NO, you can't weight it\n");
}



    void qsortic ( student* a, char *lines[], int left, int right )
    {


    int i, last;
    //printf("%d %d\n",left,right);

    if (left >= right) return;

   swapp(a, lines, left, (left + right)/2 );
    last=left;
   // printf("Printing here the left last and right %d %d %d\n",left,last,right);

    for(i = left + 1;i < right; i++)
        if (a[i].mark < a[left].mark)
        {
            printf("%s %d %s %d\n",a[left].name,a[left].mark,a[i].name,a[i].mark);
            swapp(a, lines, ++left, i);
           // printf("writing the left %d\n",left);
        }

    swapp(a, lines, left, last );
   // printf("i nave changed the last and left %d %d\n",left,last);
    qsortic(a, lines, left, last - 1);
    qsortic(a, lines, last + 1, right);

    }



    void swapp( student* a,char *lines[] ,int i,int j)
    {
         int t=a[i].mark;
             a[i].mark=a[j].mark;
             a[j].mark=t;
             swap_str(lines,i,j);
    }


    void swap_str(char *lines[],int num1,int num2)
    {

      char *f;
      f = lines[num1];
      lines[num1] = lines[num2];
      lines[num2] = f;

    }




int del (int n)
{ int t=0;
    for(int i=1;i<=(int)sqrt(n);i++)

 {


        if (n % i == 0 )
        {

              if (((int) trunc( pow( (int) sqrt(i) ,2) )==i) && (i!=1))
                {
                 if (t==0) printf("YES!!!!\n");
                 printf("%d ",i);
                 t=1;
                }

              if ((int) trunc(pow( (int)sqrt(n/i) ,2)) == (n/i))
              {

                if (t==0) printf("YES\n");

                printf("%d ",n/i);
                t=1;
              }

        }
        //if (t==0) printf("NOOO\n");
 }
 if (t==0) printf("NOOO\n");

}

int prostoe(int v)
{
    int i,y=0;
   // printf("%d %d\n",(int)trunc(sqrt(v)),v) ;

    for (i=1;i <= ((int)trunc(sqrt(v)));i=i+1)
    {
    //printf("%d ",((int)trunc(sqrt(*v)))) ;

    if (((v % i) == 0) && (i!= 1))


        y=1;
    }

if ((y == 0) && (v != 1) ) printf("%d ",v);
}


int swapping(char *a, char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;

}
int reverse_stroka(char str[])
{
    int left = -1;
    for(int i = 0; i < strlen(str); i++)
    {
        if ((left == -1) && isalnum(str[i])) left = i;

        if ((left != -1) && (!(isalnum(str[i])) || (str[i]=='\n')))
        { //printf("%d %d ",left,i-1);
       // printf("\n");
            reverse_word(str, left, i - 1);
                //for (int j=0;j<=i-1;j++)
                //printf("%c",str[j]);
            left = -1;
        }


    }



}


int reverse_word(char str[], int left, int right)
{
    for (int i = 0; i < (right-left)/2; i++)
        swapping(&str[right - i], &str[left + i]);

    for (int j=left;j<=right;j++)
         printf("%c",str[j]);
         printf(" ");

}
int decompose(int n,int k )
{
    if (k==1) return 1;
    else if ((k<0) || (n<0)) return 0;
    else return decompose(n-k,k) + decompose (n,k-1);
}


int normalize_sqrt(long n, long int * a, long int * b)
{
    assert(n > 0);

    if (((int) trunc( pow( (int) sqrt(n) ,2) ) == n))
    {
      *a = 1;
      *b = (int) sqrt(n);
    }
    else
    {
        int m = del(n);

        if (m == 0)
         {
            *a = 1;
            *b = n;
         }
        else
         {
            *b = (int) sqrt(m);
            *a = (int)(n/m);
         }
    }
}


int weighing(long x)
{
    const int WEIGHT = 4;

    assert((0 < x) && (x <= 2147483647));

    while (x > 1)
    {
        int mod = x % WEIGHT;
        switch(mod)
        {
        case 0:
            x /= WEIGHT;
            break;
        case 1:
            x--;
            x /= WEIGHT;
            break;
        case 2:
            return NO;
            break;
        case 3:
            x++;
            x /= WEIGHT;
            break;
        default:
            assert(NO);

        }

    }

    return YES;

}



int delnew (int n )
{
    int t = 0;
    int m = 0;

    for(int i = 1;i <= (int)sqrt(n);i++)

    {


        if ((n % i == 0 ))
        {

              if (((int) trunc( pow( (int) sqrt(i) ,2) ) == i) && (i != 1))
                {
                 if (t == 0) m = i;
                 //printf("sww%d \n",m);}
                 t = 1;
                }

              if ((int) trunc(pow( (int)sqrt(n/i) ,2)) == (n/i))
              {

                 if (n/i > m) m = n/i;//;printf("feeef%d\n",m);}

                //printf("%d ",n/i);
                t = 1;
              }

        }

    }
 if (t == 0) {/*printf("dcedfef");*/return 0;}
 else return m;

}


